package com.fyt.algorithm.Leecode.day8_5;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

public class MaxSlidingWindow {



    /**
     * 优先队列方案
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int [] res=new int[nums.length-k+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]!=b[0]?b[0]-a[0]:b[1]-a[1]);
        //初始化窗口
        for (int i = 0; i < k ; i++) {
            pq.offer(new int []{nums[i],i});
        }
        res[0]=pq.peek()[0];
        //开始pq进出
        for (int i = k; i <nums.length ; i++) {
            pq.offer(new int []{nums[i],i});
            while (pq.peek()[1]<i-k+1){
                pq.poll();
            }
            res[i-k+1]=pq.peek()[0];
        }


        return res;
    }

    /**
     * 单调队列方案
     * @param nums
     * @param k
     */
    public static int[] maxSlidingWindow2(int[] nums, int k){
        int []res=new int[nums.length-k+1];
        //双端队列
        Deque<Integer> dq = new ArrayDeque<>();

        //循环加入
        for (int i = 0; i < nums.length; i++) {
           //剔除窗口外,也就是窗口左边的值
            while (!dq.isEmpty() &&dq.peekFirst()<i-k+1){
                dq.pollFirst();
            }
          //维护单减队列
            while (!dq.isEmpty()&&nums[dq.peekLast()]<nums[i]){
                dq.pollLast();
            }
            //确保了当前窗口至少有一个元素
            dq.offerLast(i);
            //取出队首
            if(i>=k-1){
                res[i-k+1]=nums[dq.peekFirst()];
            }
        }



        return res;
    }

    public static void main(String[] args) {
      int[] nums={1,3,-1,-3,5,3,6,7};
      int k=3;
      int []res=maxSlidingWindow2(nums,3);
        for (int i = 0; i <res.length ; i++) {
            System.out.println(res[i]);
        }

    }

    public String toString() {
        return "MaxSlidingWindow{}";
    }
}
